package com.nine.algorithm.binarysearch;

/**
 * @author nine
 * @version 1.0
 * @description 二分查找
 * @date 24/4/23 21:50
 */
public class BinarySearch {

	/**
	 * 二分查找 平衡版
	 *
	 * 1. 左闭右开区间，i指向的可能是目标，而j指向的不是目标
	 * 2. 不在循环内找出，等范围内只剩 i 时，退出循环，在循环外比较 a[i] 和 target
	 * 3. 循环内的平均比较次数减少了
	 * 4. 时间复杂度 O(log(n))
	 *
	 * @param a
	 * @param target
	 * @return
	 */
	public static int binarySearch3(int[] a, int target) {
		// 边界
		int i = 0, j = a.length;
		// 范围内，待查找的数据个数，当数据大于1时，在循环内，否则退出循环，此时仅剩一个数据未比较，就是a[i]
		while (1 < j - i) {
			int m = (i + j) >>> 1;
			if (target < a[m]) {
				j = m;
			}
			else {
				i = m;
			}
		}
		if (a[i] == target) {
			return i;
		}
		return -1;
	}


	/**
	 * 二分查找改进版
	 *
	 * @param a      待查找的升序数组
	 * @param target 待查找的目标值
	 * @return 找到则返回索引
	 * 找不到返回 -1
	 */
	public static int binarySearchAlternative(int[] a, int target) {
		// 设置指针和初值【改动1】
		int i = 0, j = a.length;
		// 范围内有数据【改动2】
		while (i < j) {
			int m = (i + j) >>> 1;
			// 目标在左边【改动3】
			if (target < a[m]) {
				j = m;
			}
			// 目标在右边
			else if (a[m] < target) {
				i = m + 1;
			}
			// 找到了
			else if (target == a[m]) {
				return m;
			}
		}
		return -1;
	}

	/**
	 * 问题一：为什么是 i<=j ? 意味着区间内存在未比较的元素，而不是i<j?
	 * i==j 意味着 i，j 他们指向的元素也会参与比较
	 * i<j 只意味着 m 指向的元素参与比较
	 *
	 * 问题二：(i+j)/2 有没有问题？
	 * int类型的最大值，如果二分法在右边，相加，会溢出，所以需要用位运算来代替除法
	 *
	 */


	/**
	 * 二分查找基础版
	 *
	 * @param a      待查找的升序数组
	 * @param target 待查找的目标值
	 * @return 找到则返回索引
	 * 找不到返回 -1
	 */
	public static int binarySearchBasic(int[] a, int target) {
		// 设置指针和初值
		int i = 0, j = a.length - 1;
		// 范围内有数据
		while (i <= j) {
			int m = (i + j) >>> 1;
			// int m = (i + j) / 2;
			// 目标在左边
			if (target < a[m]) {
				j = m - 1;
			}
			// 目标在右边
			else if (a[m] < target) {
				i = m + 1;
			}
			// 找到了
			else if (target == a[m]) {
				return m;
			}
		}
		return -1;
	}

	/**
	 * 二分查找基础版【自己写的】
	 *
	 * @param a      待查找的升序数组
	 * @param target 待查找的目标值
	 * @return 找到则返回索引
	 * 找不到返回 -1
	 */
	public static int binarySearchBasicSelf(int[] a, int target) {
		int i = 0;
		int j = a.length - 1;
		while (i <= j) {
			// 不存在，则返回-1
			if (a[0] > target || a[a.length - 1] < target) {
				return -1;
			}
			int k = (i + j) / 2;
			if (target < a[k]) {
				j = k - 1;
			}
			else if (target > a[k]) {
				i = k + 1;
			}
			else if (target == a[k]) {
				return k;
			}

		}
		return -1;
	}


}
